Associated Type Synonyms

著者

Manuel Chakravarty

Gabriele Keller

Simon Peyton Jones

2005/1

大まかな流れ

Abstract

1 Introduction

2 Applications of Associated Type Synonyms

3 The Programmer's-eye view

4 The Type System

5 Type Inference

6 Functional Dependencies

7 Other related work

8 Conclusions and further work

References

読みメモ

https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/at-syns.pdf

fun depsとassocieated type synonymの関連、みたいなやつか

コレ読みたいやつだmrsekut.icon

fun depsとの差異を知りたいだけなので全部を読む気はないmrsekut.icon

ムズイ。理解できないmrsekut.icon

これ前提として、

hsにfun depsが実装済み、で、type familyがまだない？もしくはtype familyはあるがAssociated typesがまだない？状況で書かれたものっぽい

GHC 年表見たがこの辺の時系列よくわからなかったmrsekut.icon

Abstract

multi paramな型クラスを使用する場合にFunctionalDependenciesがよく使われるが、プログラマの意図が伝わりにくい

そこで、型クラス内にType Familyを定義するAssociated Type Familyを提案する

これは、fun depsに比べて明示的であり、fun depsの代替手段になる

1 Introduction

fun deps周りの議論をするときにCollects型クラスを扱うのってあるあるなのか？mrsekut.icon

ということは、Type Classes with Functional Dependenciesを読んでるのとかは割とアタリマエという感じなんかな

code:hs

class Collects e where

type Elem e

empty :: e

insert :: Elem e -> e -> e

toList :: e -> Elem e

ちなみにType Classes with Functional Dependenciesに載ってたやつ

code:元のmulti paramのやつ.hs

class Collects e ce where

empty :: ce -- 空のcollectionを作成

insert :: e -> ce -> ce -- 追加

member :: e -> ce -> Bool -- 存在確認

code:fun depsで書き換えたやつ.hs

class Collects e c | c -> e where

empty :: c

insert :: e -> c -> c

member :: e -> c -> Bool

membership testってなに #??

Elemとは何か？

Elem cは、collection type cの要素となる型

Elemは、collection typeをelement typeに変える型レベル関数とみなせる

Elemはnon-parametoricである

However, just as insert is non-parametric (its implementation varies depending on c), so is Elem.

> For example,Elem [e] is e, but Elem BitSet is Char.

cはassociated type Elem cを持つ

具体定期にどういう型なのかはclass宣言時には指定しない

isntance宣言時に与えられる

code:hs

instance Eq e => Collects e where

type Elem e = e

instance Collects BitSet where

type Elem BitSet = Char

instance (Collects c, Hasable (Elem c)) => Collects (Array Int c) where

type Elem (Array Int c) = Elem c

fun depsと比較してどちらが良いのかを言いたいわけではない

our goal here is only to describe and characterise a new pointin the design space of type classes.

2 Applications of Associated Type Synonyms

Associated Type Familyの有用性とsemanticsの調査

code:hs

{-# LANGUAGE TypeFamilies #-}

{-# LANGUAGE FlexibleInstances #-}

data I f = I f

data C f = C f

data S f = S String f

formatSpec :: S (I (S (C String)))

formatSpec = S "Int: " $ I $ S ", Char: " $ C $ "."

class Format fmt where

type Sprintf fmt

sprintf' :: String -> fmt -> Sprintf fmt

instance Format String where

type Sprintf String = String

sprintf' prefix str = prefix ++ str

instance Format a => Format (I a) where

type Sprintf (I a) = Int -> Sprintf a

sprintf' prefix (I a) = \i -> sprintf' (prefix ++ show i) a

instance Format a => Format (C a) where

type Sprintf (C a) = Char -> Sprintf a

sprintf' prefix (C a) = \c -> sprintf' (prefix ++ c) a

-- errorになる

instance Format a => Sprintf (S a) where

type Sprintf (S a) = Sprintf a

sprintf' prefix (S str a) = sprintf' (prefix ++ str) a

sprintf :: Format fmt => fmt -> Sprintf fmt

sprintf = sprintf' ""

3 The Programmer's-eye view

Associated Type Familyが決定可能である場合に型推論を維持するために必要な構文上の制約について説明

4 The Type System

Associated Type Familyをサポートする型システムの提供

System F styleで記述したものを載せる

5 Type Inference

Associated Type Familyから生じるnon-syntactic equalitiesを処理できる型推論アルゴリズムの提示

これはA theory of qualified typesのqualified typeの拡張である

6 Functional Dependencies

fun depsとの比較

fun depsには3つのvariantが存在するので比較は複雑になる

1 Type Classes with Functional Dependenciesで記述されたもの

決定可能である

2 GHCで実装されているもの

決定可能でない

3 A theory of overloadingで形式化されたもの

Peter J. Stuckey

Martin Sulzmann

よくわからんが、一部を妥協することで1,2より一般的になっている

決定可能である

Associated Type Familyも決定可能である

7 Other related work

Hindley-Milner, ML moduleについての関連

8 Conclusions and further work

References